﻿using System;

/// <summary>
/// Specifications in human readable sentences, related to the Board in 'Katamino'
/// * The Board is a rectangle, with Width Width and Height Height
/// * Typical dimensions (HxW) are (5x12) and (6x10)
/// * This adds up to 60 Squares in the Board, which equals the number of squares in 12 katamino pieces.
/// ** generalize to (3x20), (4x15), (7x9) and (8x8) (with optional holes) later
/// ** but leave it to those dimensions, so we can use a 64 bit vector for fast calculations
/// </summary>
namespace Katamino
{
    public class Board
    {
        /// <summary>
        /// The Width of the Board
        /// </summary>
        public int Width;

        /// <summary>
        /// The Height of the Board
        /// </summary>
        public int Height;

        // Instance Data
        public int[,] D;  // penta cover data 1..12, or 0 if empty

        /// <summary>
        /// The fields that are covering the board encoded in UInt64 bits.
        /// </summary>
        public UInt64 BitCover;

        /// <summary>
        /// Functionality to make adding penta's to Board and backtracking easier
        /// </summary>
        public Board Parent;

        public UInt64 UsedPentas;
        public UInt64 UnusedPentas;
        public int FirstFree; // index in BitCover vector of first free element

        // constructor
        public Board()
        {
            Width = 0;
            Height = 0;
            UsedPentas = 0;
            UnusedPentas = (1 << 13) - 1 - 1; // Set bits 1..12. Leave bit 0 for starting board cover.
            FirstFree = 0;
            D = new int[Width, Height];
        }

        /// <summary>
        /// Create an empty Board
        /// </summary>
        /// <param name="w">Width of the Board</param>
        /// <param name="h">Height of the Board</param>
        public Board(int w, int h)
        {
            Width = w; // Set the 'global' Board size
            Height = h;
            UsedPentas = 0;
            UnusedPentas = (1 << 13) - 1 - 1; // Set bits 1..12. Leave bit 0 for starting board cover.
            FirstFree = 0;

            D = new int[Width, Height]; // initialize Board data, as an empty array
            BitCover = (UInt64)0;
        }

        /// <summary>
        /// Create an empty Board
        /// </summary>
        /// <param name="w">Width of the Board</param>
        /// <param name="h">Height of the Board</param>
        public Board(int w, int h, UInt64 bitmask)
        {
            Width = w; // Set the 'global' Board size
            Height = h;

            BitCover = bitmask; // bits in this mask will have no Id
            UsedPentas = 0;
            FirstFree = 0;
        }

        /// <summary>
        /// FirstFree returns TRUE if the Board has a free square.
        /// fh, fw are set to the location of the found square.
        /// There are a few variants of this algorithm, to experiment if it is faster to fill from the small or the wide side.
        /// </summary>
        /// <returns></returns>
        public int firstFree()
        {
            FirstFree = 0;
            return nextFree();
        }

        public int nextFree()
        {
            // bit implementation
            for (; (FirstFree < (this.Width * this.Height)) && (((BitCover >> FirstFree) & 1) == 1); FirstFree++)
            {
                // just loop until a new free place is found
            }

            return FirstFree;
        }

        /// <summary>
        /// Add a Penta to the board, automatically at the first free place.
        /// </summary>
        /// <param name="penta">
        /// </param>
        /// <returns>
        /// Board with new penta if possible
        /// null if not possible
        /// </returns>
        public Board AddPenta(Penta penta, int p)
        {
            Board result = null;

            var overlap = BitCover & (penta.Bits << p);
            var allowed = (penta.Allowed >> p) & 1;

            if (overlap == 0 && allowed == 1)
            {
                result = new Board
                {
                    Parent = this,
                    Width = this.Width,
                    Height = this.Height,
                    BitCover = this.BitCover | (penta.Bits << p),
                    UsedPentas = this.UsedPentas | ((UInt64)1 << penta.Id),
                    UnusedPentas = this.UnusedPentas - (this.UnusedPentas & ((UInt64)1 << penta.Id)),
                    FirstFree = this.FirstFree,
                };
                result.FirstFree = result.nextFree();
            }

            return result;
        }

        public Board AddPenta(Penta penta)
        {
            return AddPenta(penta, this.FirstFree);
        }
    }
}